package 中等.动态规划.子序列;

/**
 * 给你一个整数数组 nums，返回 nums 中最长等差子序列的长度。
 * 回想一下，nums 的子序列是一个列表 nums[i1], nums[i2], ...,
 * nums[ik] ，且 0 <= i1 < i2 < ... < ik <= nums.length - 1。
 * 并且如果 seq[i+1] - seq[i]( 0 <= i < seq.length - 1) 的值
 * 都相同，那么序列 seq 是等差的。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/longest-arithmetic-subsequence
 */
public class 最长等差数列_1027 {

    public static void main(String[] args) {

        System.out.println(longestArithSeqLength(new int[]{9, 4, 20, 1, 15, 3, 10, 5, 8}));

    }

    /**
     * 枚举等差数列差值+动态规划
     * 1，0 <= nums[i] <= 500，那么等差数列的差值 diff 范围为 [-500,500]
     * 2，现在已知差值，那么 num[i] 的前面一个数确定 = nums[i] + diff
     * 定义 dp[i] 表示以数字 i 结尾的最长等差数列长度是多少，那么
     * 状态转移方程
     * dp[i] = dp[i+diff] +1
     */
    public static int longestArithSeqLength(int[] nums) {
        int ans = 0;
        for (int diff = -500; diff <= 500; diff++) {
            int[] dp = new int[1501];
            for (int i = 0; i < nums.length; i++) {

                dp[nums[i] + 500] = dp[nums[i] + diff + 500] + 1;

                ans = Math.max(ans, dp[nums[i] + 500]);
            }
        }
        return ans;
    }

}
